<html>
<head><meta http-equiv="Content-Type" content="text/html; charset=GBK">
<title>Lab 1: Lexer and Parser</title>
<link rel="stylesheet" href="../labs.css" type="text/css">
</head>

<body>
<table width="100%">
<tbody>
  <tr>
<td>
<h1>Lab 1: F# and Interpreter</h1>
<hr>

<h3>Lab Overview</h3>
In this series labs in this course, you'll design and implement
a production-quality
compiler, called <kbd>jcc</kbd> for a non-trivial subset of the Java programming
language. There are six labs planned, and this is the first lab.

<p>
In this lab, you'll implement the frond-end for <kbd>jcc</kbd>: the
lexer and the parser. In the second lab, you'll implement the
abstract syntax tree and elaboration. In the 3rd lab, you'll
implement java bytecode generation. The 4th lab is about optimization.
The 5th lab is about generating code for MIPS and Pentium. The 6th
lab is on garbage collection.

<h3>Software Setup</h3>
<p>
In this lab, the implementaion language we'll use is F#, check
<a href="http://staff.ustc.edu.cn/~bjhua/courses/compiler/2012/tools.html">here</a>
for the installation issues. 

<p>
Also make sure you've installed Java compiler and runtime (version 7.0).

<h3>Version control and SVN</h3>
The files you will need for this and subsequent lab assignments 
in this course are controlled and distributed using the Subversion
version control system. To learn more about Subversion, take a look at 
<a href="http://subversion.tigris.org/">its website</a>. You don't
need to install or configure Subversion yourself in this course, for
we've set it up accordingly. But you may use it in your future
projects.

<p>
For this course, you'll use the
<a href="http://tortoisesvn.net/downloads.html">tortoise SVN client</a>, which is
easily installed. Make sure you installed the latest version (1.7.4) of subversion, for
the older version is not compatiable with the current code repository. 

<p>
For those who have not used tortoise SVN before, you should take a look
at this introduction article.

<h3>Getting Started</h3>
In each lab, we'll offer you a code skeleton to modify and enhance.
This year, we've decided to put the code repository on Google (for
this courseware is also open-source). Download the code repository here:
...

<p>
If this does not work for you, please let us know.

<h3>Hand-in Procedure</h3>
When you finished your lab, zip you solutions and submit to the
<a href="">school's information system</a>.

<h1>Part A: Binary search trees</h1>


<h1>Part B: Straight-line program interpreter</h1>
<p>
This part requires you to write a simple program analyzer and 
interpreter for a straight-line programming language <kbd>SLP</kbd>. This 
exercise serves as an introduction to environments (symbol 
tables mapping variable-names to information about the variables);
to abstract syntax (data structures representing the phrase 
structure of programs); to recursion over tree data structures,
useful in many parts of a compiler; and to a functional style of 
programming without assignment statements. 

<p>
The definition of SLP language is in grammar 1.3 in chapter 1. You
should read that part carefully and make sure you understand
the meanings of each language struct. Here
is a sample program
</p>
<pre>     
     a = 5+3; 
     b = (print(a, a-1), 10*a); 
     print(b);
</pre>
which will be used throughout this part of the lab. 

<p>When executed, this program print
<pre>
8 7
80
</pre>
on standard out (the screen) when run. That is, each <code>print</code>
will print each of its argument in turn, separated by a space, terminated
by a new line. If there is no aurguments to the <code>print</code>
statement, it merely prints a new line.

<p>
In this lab, you will write two components for this simple programming
language: a simple program analyzer and 
an interpreter.

<p>
Now browse the code we offered. Here is a brief 
discription of these files:

<table valign="top" border="1" >
  <tr>
    <td>slp.fs:</td>
    <td>data structures to define SLP, whose constructors 
      represent abstract syntax tree nodes</td>
  </tr>

  <tr>
    <td>testprog.fs:</td>
    <td>a sample program of SLP, which shows how to construct AST from "slp.fs" given above </td>
  </tr>

  <tr>
    <td>maxarg.fs:</td>
    <td>scan AST of a program, and return the 
      maximum number of arguments of any print statement within 
      any (sub-)expression of the program</td>
  </tr>

  <tr>
    <td>interp.fs:</td>
    <td>scan AST of a program, and interpret the program (i.e., should
    simulate the print behaviour of the scanned program</td>
  </tr>

  <tr>
    <td>main.fs:</td>
    <td>the entry point of whole program</td>
  </tr>
</table>

<p>
For those who are familar with C, C++ or Java, but new to F#, here
are some further notes to help you:
<ul>
  <li>F# is NOT style-free, that is, separators such as spaces, tabs and new lines
    may play a significant role in source code. If you don't obey
    these roles, your code won't even compile. For a quick overview
    of the rules, take a look at 
    <a href="http://msdn.microsoft.com/en-us/library/dd233191.aspx">the code formatting
      guide lines</a>. Remember to check this, when 
    you code don't compile.
  <li>F# has NO notion of "main" functions, that is, there is no
    conventional "main" or "Main" functions in a program as entry
    point (just illustrated by the lab code 
    we have offered you). Instead, the execution starts from
    the last file in a project (in the code above, the file <code>test.fs</code>).
</ul>

<h3>Pretty printer</h3>
A pretty printer, as its name suggests, will print some out, but
in a somewhat pretty form. It's a classical problem with decades
of history and numerous interesting applications. Read more about 
pretty printing in computer science 
<a href="http://en.wikipedia.org/wiki/Prettyprint">on the wiki</a>. 
Pretty-print the abstract syntax tree out has the great importance
for debugging: if the printed tree is the same as the desired
source, then we are on the right way.

<div class="required">
<p><span class="header">Exercise 2.</span>
Read the code in file <code>pp.fs</code>. The algorithm for
pretty printing has been (alomost) written for you, make sure you read
and understand the code there. Later in the course, you'll
encouter more fancy pretty printing algorithms, so this one
is a good start point.

<p>
After you read this code, try build the code and run it (in VS2010
, just press
<code>Ctrl+F5</code>), and check how the pretty printing code works.

<p>
Now, it's time for you to write some code. The code printed out
looks like the left one, which is different from the one on
the right as expected. What's the difference? And this difference reveals
that there exists some bug in current code. Try find these bugs
and fix them.
<table>
  <tr>
    <td>
      <pre>
        a = 5+3; 
        b = (print(a, a-1,), 10*a); 
        print(b,);
      </pre>
    </td>
    <td>
      <pre>
        a = 5+3; 
        b = (print(a, a-1), 10*a); 
        print(b);
      </pre>
    </td>
  </tr>
</table>
Dont' forget to test your code when you finished.
</div>

<div class="challenge">
<p><span class="header">Challenge!</span>
There are many more fancy pretty printing algorithms, besides the one
we've offered you. 
<a href="ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/79/770/CS-TR-79-770.pdf">Derek Oppen's paper</a>
is among the first ones to
present a pretty printing routine, based on an imperative style. Later
in 1997, Phillip Wadler presents a
<a href="http://homepages.inf.ed.ac.uk/wadler/papers/prettier/prettier.pdf">functional style
algorithm</a>. 

<p>
Read these papers (or others on your choice), and implement a
pretty printing library based on the
algorithms there. Try your library for printting Slp. Hint: as
you'are using F#, so Wadler's algorithm may be a better candidate.
</div>

<h3>Maximum Number of Arguments</h3>
<p>
There is only one kind of function here in Slp: <code>print</code>, and
<code>print</code> can take a variable number of arguments. For
instance, the first <code>print</code> in previous program
<pre>
        a = 5+3; 
        b = (print(a, a-1), 10*a); 
        print(b);
</pre>
has 2 arguments, whereas the second <code>print</code> only has
1 argument. So the maximum number of arguments in this program is 2.

<div class="required">
<p><span class="header">Exercise 3.</span>
Finish the code in file <code>maxarg.fs</code>. The code you should modify looks like:
<pre>  raise Unimplement
</pre>
So you should find all places marked as this and replace them with your code.
</div>

<h3>Interpreter</h3>
<p>
There is only one kind of function here in Slp: <code>print</code>, and
<code>print</code> can take a variable number of arguments. For
instance, the first <code>print</code> in previous program
<pre>
        a = 5+3; 
        b = (print(a, a-1), 10*a); 
        print(b);
</pre>
has 2 arguments, whereas the second <code>print</code> only has
1 argument. So the maximum number of arguments in this program is 2.

<div class="required">
<p><span class="header">Exercise 4.</span>
Finish the code in file <code>interp.fs</code>. The code you should modify looks like:
<pre>  raise Unimplement
</pre>
So you should find all places marked as this and replace them with your code.
</div>

<h3>Optimization</h3>
<p>
The primary purpose for optimization is to make programs consume
less memory, run faster, etc.. Normally, optimizations are
performed on intermediate representation such as three-address
code or. But as we've discussed the abstract syntax tree
for the language Slp, we can also experiment some simple
optimizations.

<p>
<i>Constant folding</i> is an optimization that calculates
(at compile-time) the result of operations on constants (integer or real
literals, static addresses, etc..). For instance, consider
the previous sample program again on the left, and the result
of constant folding is on the right:
<table>
  <tr>
    <td>
      <pre>
        a = 5+3; 
        b = (print(a, a-1), 10*a); 
        print(b);
      </pre>
    </td>
    <td>
      <pre>
        a = 8; 
        b = (print(a, a-1), 10*a); 
        print(b);
      </pre>
    </td>
  </tr>
</table>

<div class="required">
<p><span class="header">Exercise 5.</span>
Write a function
<pre>  let constFold (s: Slp.stm): Slp.stm = ...
</pre>
which performs constant folding. We have NOT provide
you a skeleton file, so you should create one if necessary. Think the algorithm
carefully before writing your code.
</div>

<p>
<i>Constant propogation</i> is an optimization that substitute
the compile-time constant variable with that constant. For instance, consider
the above sample program again (on the left, which is after constant
folding), and the result
of constant propogation is on the right:
<table>
  <tr>
    <td>
      <pre>
        a = 8; 
        b = (print(a, a-1), 10*a); 
        print(b);
      </pre>
    </td>
    <td>
      <pre>
        a = 8; 
        b = (print(8, 8-1), 10*8); 
        print(b);
      </pre>
    </td>
  </tr>
</table>

<p>
An interesting point is that, as you may observe in the above
example, after this optimization, there may exist chances
for further optimizations (say, constant folding again). So, for
this sample program, there is a cycyle on the two optimizations:
constant folding -> constant propagation -> constant folding ->
constant propogation -> ...

<p>
Is this an infinite loop? That is, how do you know when this
cycyle should stop?

<div class="required">
<p><span class="header">Exercise 6.</span>
Write a function
<pre>  let constProp (s: Slp.stm): Slp.stm = ...
</pre>
which performs constant propogation. Also you should create a new
file if necessary. How should you know whether there is chance to
perform another pass of constant folding? Should you do constant
folding again?
</div>

<p>
<i>Dead code elimination</i> optimization tries to eliminate 
<i>useless</i> code from a given program. For now, we have
not given a formal definition on what is <i>useless</i>, which
will be discusses in a later phase of this course. But, for the
Slp language, the notion of useless is simple: if an assignment
statement assigns value to some variable <i>x</i>, but <i>x</i>
will never be used in futher, then <i>x</i> is useless. For instance, the
variable <code>a</code> in the following left prorgram is
useless, but <code>b</code> is not useless. As a result, one
can eliminate the assignment statement to <code>a</code>, obtaining
the right result:
<table>
  <tr>
    <td>
      <pre>
        a = 8; 
        b = (print(a, a-1), 10*a); 
        print(b);
      </pre>
    </td>
    <td>
      <pre>
        <del>a = 8;</del>
        b = (print(8, 8-1), 10*8); 
        print(b);
      </pre>
    </td>
  </tr>
</table>

<p>
Can the above right program be further optimized? If so, how?

<div class="required">
<p><span class="header">Exercise 7.</span>
Write a function
<pre>  let deadCode (s: Slp.stm): Slp.stm = ...
</pre>
which performs dead code elimination. 

<p>Now, you can run your interpr again on the final optimized
version of your program. The interpreter should print the same
values as before.
</div>

<h3>Handin</h3>
This completes the lab. Remember to hand in your solution to 
the information system. How long does it take you to finish this lab?

</td>
</tr>
  
</tbody>
</table>


</body>
</html>
